board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word="ABCB"
direction=[-1,0,1,0,-1]
def dfs(board,word,r,c,p,have_used,have_successful):
    #递归出口
    if p==len(word):
        have_successful.append("True")
        return None
    # print("当前处理的是第{0}个字符".format(p))
    # print("开始向四个相邻点扩张，寻找切合点....")
    for i in range(4):
        x,y=r+direction[i],c+direction[i+1]
        # print("搜索点{0}-{1}位置".format(x, y))
        if x>=0 and x<len(board) and y>=0 and y<len(board[0]) and have_used[x][y]==False:
            #这个位置的字符还没有被用掉
            if board[x][y]==word[p]:
                #当前位置是符合要求的
                have_used[x][y]=True
                # print("在相邻点中找到了-{0}行-{1}列-点符合条件,对应的字符是{2}".format(x,y,word[p]))
                dfs(board,word,x,y,p+1,have_used,have_successful)
                have_used[x][y]=False
            # print("第{0}行{1}列-这个点不满足条件，其字符值是--{2}--".format(x,y,board[x][y]))
            #其余情况下什么也不做
def exist(board,word):
    n,m=len(board),len(board[0])
    have_used=[[False for _ in range(m)] for _ in range(n)]
    # print(have_used)
    have_successful=[]
    for i in range(n):
        for j in range(m):
            #双重for循环来遍历图
            if board[i][j]==word[0]:
                # print("在第{0}行,第{1}列的位置找到了一个起点，开始进入递归".format(i,j))
                #找到了进入点
                have_used[i][j]=True
                # print("开始递归....")
                dfs(board,word,i,j,1,have_used,have_successful)
                if len(have_successful)>0:
                    return True
                #回溯
                have_used[i][j]=False
    return False
print(exist(board,word))